#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
const int N = 1e6 + 5;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

void solve() {
    ll a, b;
    cin >> a >> b;
    if (b == 1) {
        cout << "-1" << endl;
        return;
    }
    ll d = b;
    while (true) {
        ll g = gcd(a, d);
        if (g == 1) break;
        d /= g;
    }
    if (d == 1) {
        cout << "-1" << endl;
    } else {
        cout << d << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}